package class10;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 数组实现LRU
 */
public class Code10_LRU_Array {
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(3);
        lruCache.put(1, 11);
        lruCache.put(2, 22);
        lruCache.put(3, 33);
        lruCache.put(4, 44);
        lruCache.put(5, 55);
        System.out.println("lruCache.nodeList = " + lruCache.nodeList);
        lruCache.put(4, 42);
        lruCache.put(6, 6);

        System.out.println("lruCache.nodeList = " + lruCache.nodeList);
        System.out.println("lruCache.get(4) = " + lruCache.get(4));
    }

    private static class LRUCache {
        private Map<Integer, Integer> keyNodesMap;

        private LRUArray nodeList;

        private final int capacity;

        public LRUCache(int capacity) {
            keyNodesMap = new HashMap<>();
            nodeList = new LRUArray();
            this.capacity = capacity;
        }

        public int get(int k) {
            if (keyNodesMap.containsKey(k)) {
                Integer v = keyNodesMap.get(k);
                nodeList.moveNodeToTail(k, v);
                return v;
            }
            return -1;
        }

        public void put(int k, int v) {
            if (keyNodesMap.containsKey(k)) {
                nodeList.moveNodeToTail(k, v);
                keyNodesMap.put(k, v);
            } else {
                if (capacity == keyNodesMap.size()) {
                    int i = nodeList.remveHead();
                    keyNodesMap.remove(nodeList.getKey(i));
                }
                keyNodesMap.put(k, v);
                nodeList.addNode(k, v);
            }
        }
    }

    /**
     * 数组方式实现LRU
     */
    private static class LRUArray {
        private int l, r;
        private int[] arr;
        private int[] vals;

        public LRUArray() {
            l = r = 0;
            arr = new int[1000000];
            vals = new int[1000000];
        }

        public int getKeyIndex(int k) {
            for (int i = l; i < r; i++) {
                if (arr[i] == k) {
                    return i;
                }
            }
            return -1;
        }

        public int getKey(int index) {
            return arr[index];
        }

        // 添加元素
        public void addNode(int k, int v) {
            if (r == -1) {
                return;
            }
            arr[r] = k;
            vals[r++] = v;
        }

        // 删除尾元素
        public int remveHead() {
            if (l == r) {
                return -1;
            }
            return l++;
        }

        /**
         * 将node节点移动存尾
         */
        public void moveNodeToTail(int key, int v) {
            int keyIndex = getKeyIndex(key);
            if (keyIndex == r - 1) { // 如果节点在尾部，则不用动
                return;
            }
            if (keyIndex == l) { // 如果节点在头部，则头部节点前进到下一个节点
                l++;
            } else {
                arr[keyIndex] = -1;
                System.arraycopy(arr, keyIndex + 1, arr, keyIndex, r);
                System.arraycopy(vals, keyIndex + 1, vals, keyIndex, r);
                r--;
            }
            addNode(key, v);
        }

        @Override
        public String toString() {
            return Arrays.toString(Arrays.copyOfRange(vals, l, r));
        }
    }
}



